2011): “A Revealed Preference Approach to Computational Complexity

ABSTRACT. Recent results in complexity theory suggest that various economic theories require agents to solve computationally intractable problems. However, such results assume the agents are optimizing explicit utility functions, whereas the economic theories merely assume the agents behave rationally, where rational behavior is defined via some optimization problem. Might making rational choices be easier than solving the corresponding optimization problem? For at least one major economic theory, the theory of the consumer (which simply postulates that consumers are utility maximizing), we find this is indeed the case. In other words, we prove the possibly surprising result that computational constraints have no empirical consequences for consumer choice theory. Our result motivates a general approach for posing questions about the empirical content of computational constraints: the revealed preference approach to computational complexity. This approach complements the conventional worst-case view of computational complexity in important ways, and is methodologically close to mainstream economics. 1